import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-08-03
 * Time: 21:08
 */
//https://leetcode.cn/problems/copy-list-with-random-pointer/submissions/649520996/
//复制随机链表
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }

    public static void fun(Node p){
        while(p!=null){
            System.out.print(p.val+"  ");
            if(p.random==null){
                System.out.print("null");
            }
            else{
                System.out.print(p.random.val);
            }
            System.out.println(" ");
            p=p.next;
        }
    }
}
public class Test {
    public static Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        Node p=head;
        HashMap<Node,Node> map=new HashMap();
        while(p!=null){
            Node n=new Node(p.val);
            map.put(p,n);
            p=p.next;
        }
        p=head;
        while(p!=null){
            map.get(p).next=map.get(p.next);
            map.get(p).random=map.get(p.random);
            p=p.next;
        }
        return map.get(head);
    }

    public static void main(String[] args) {
        Node p0=new Node(7);
        Node p1=new Node(13);
        Node p2=new Node(11);
        Node p3=new Node(10);
        Node p4=new Node(1);
        p0.next=p1;
        p1.next=p2;
        p2.next=p3;
        p3.next=p4;
        p0.random=null;
        p1.random=p0;
        p2.random=p4;
        p3.random=p2;
        p4.random=p0;
        Node p=copyRandomList(p0);
        Node.fun(p);
    }
}
